// 排序算法
export const sortAlgorithms = {
  // 快速排序
  quickSort<T>(arr: T[], compare: (a: T, b: T) => number = (a, b) => (a as any) - (b as any)): T[] {
    if (arr.length <= 1) return arr;

    const pivot = arr[Math.floor(arr.length / 2)];
    const left = arr.filter(x => compare(x, pivot) < 0);
    const middle = arr.filter(x => compare(x, pivot) === 0);
    const right = arr.filter(x => compare(x, pivot) > 0);

    return [...this.quickSort(left, compare), ...middle, ...this.quickSort(right, compare)];
  },

  // 归并排序
  mergeSort<T>(arr: T[], compare: (a: T, b: T) => number = (a, b) => (a as any) - (b as any)): T[] {
    if (arr.length <= 1) return arr;

    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid);

    return this.merge(this.mergeSort(left, compare), this.mergeSort(right, compare), compare);
  },

  merge<T>(left: T[], right: T[], compare: (a: T, b: T) => number): T[] {
    const result: T[] = [];
    let leftIndex = 0;
    let rightIndex = 0;

    while (leftIndex < left.length && rightIndex < right.length) {
      if (compare(left[leftIndex], right[rightIndex]) <= 0) {
        result.push(left[leftIndex]);
        leftIndex++;
      } else {
        result.push(right[rightIndex]);
        rightIndex++;
      }
    }

    return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
  },

  // 堆排序
  heapSort<T>(arr: T[], compare: (a: T, b: T) => number = (a, b) => (a as any) - (b as any)): T[] {
    const result = [...arr];
    const n = result.length;

    // 构建最大堆
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
      this.heapify(result, n, i, compare);
    }

    // 从堆中提取元素
    for (let i = n - 1; i > 0; i--) {
      [result[0], result[i]] = [result[i], result[0]];
      this.heapify(result, i, 0, compare);
    }

    return result;
  },

  heapify<T>(arr: T[], n: number, i: number, compare: (a: T, b: T) => number): void {
    let largest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;

    if (left < n && compare(arr[left], arr[largest]) > 0) {
      largest = left;
    }

    if (right < n && compare(arr[right], arr[largest]) > 0) {
      largest = right;
    }

    if (largest !== i) {
      [arr[i], arr[largest]] = [arr[largest], arr[i]];
      this.heapify(arr, n, largest, compare);
    }
  },
};

// 搜索算法
export const searchAlgorithms = {
  // 二分查找
  binarySearch<T>(
    arr: T[],
    target: T,
    compare: (a: T, b: T) => number = (a, b) => (a as any) - (b as any),
  ): number {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      const comparison = compare(arr[mid], target);

      if (comparison === 0) {
        return mid;
      } else if (comparison < 0) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }

    return -1;
  },

  // 线性查找
  linearSearch<T>(
    arr: T[],
    target: T,
    compare: (a: T, b: T) => number = (a, b) => (a as any) - (b as any),
  ): number {
    for (let i = 0; i < arr.length; i++) {
      if (compare(arr[i], target) === 0) {
        return i;
      }
    }
    return -1;
  },

  // KMP字符串搜索
  kmpSearch(text: string, pattern: string): number[] {
    const matches: number[] = [];
    if (pattern.length === 0) return matches;

    // 构建失配表
    const lps = new Array(pattern.length).fill(0);
    let len = 0;
    let i = 1;

    while (i < pattern.length) {
      if (pattern[i] === pattern[len]) {
        len++;
        lps[i] = len;
        i++;
      } else {
        if (len !== 0) {
          len = lps[len - 1];
        } else {
          lps[i] = 0;
          i++;
        }
      }
    }

    // 搜索模式
    let j = 0;
    i = 0;

    while (i < text.length) {
      if (pattern[j] === text[i]) {
        j++;
        i++;
      }

      if (j === pattern.length) {
        matches.push(i - j);
        j = lps[j - 1];
      } else if (i < text.length && pattern[j] !== text[i]) {
        if (j !== 0) {
          j = lps[j - 1];
        } else {
          i++;
        }
      }
    }

    return matches;
  },
};

// 动态规划示例：斐波那契数列
export const fibonacci = (n: number, memo: Record<number, number> = {}): number => {
  if (n < 0) throw new Error('Input must be non-negative');
  if (n <= 1) return n;
  if (memo[n]) return memo[n];

  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  return memo[n];
};

// 贪心算法示例：找零钱问题
export const makeChange = (amount: number, coins: number[]): number[] | null => {
  if (amount < 0) throw new Error('Amount must be non-negative');
  if (coins.length === 0) throw new Error('Coins array cannot be empty');

  const result: number[] = [];
  let remaining = amount;

  // 确保硬币是有效的且按降序排序
  const validCoins = coins.filter(coin => coin > 0).sort((a, b) => b - a);

  if (validCoins.length === 0) {
    throw new Error('No valid coins provided');
  }

  for (const coin of validCoins) {
    while (remaining >= coin) {
      result.push(coin);
      remaining -= coin;
    }
  }

  // 如果无法完全找零，返回null
  return remaining === 0 ? result : null;
};

// 图算法：深度优先搜索
export type Graph = Record<string, string[]>;

export const depthFirstSearch = (
  graph: Graph,
  start: string,
  visited: Set<string> = new Set(),
): string[] | null => {
  // 验证起始节点是否存在
  if (!(start in graph)) {
    return null;
  }

  const result: string[] = [];

  const dfs = (vertex: string) => {
    visited.add(vertex);
    result.push(vertex);

    for (const neighbor of graph[vertex] || []) {
      if (!visited.has(neighbor)) {
        // 验证邻居节点是否存在
        if (!(neighbor in graph)) {
          throw new Error(`Invalid graph: node ${neighbor} not found`);
        }
        dfs(neighbor);
      }
    }
  };

  try {
    dfs(start);
    return result;
  } catch (error) {
    return null;
  }
};

// 字符串算法：KMP模式匹配
export const kmpSearch = (text: string, pattern: string): number => {
  if (typeof text !== 'string' || typeof pattern !== 'string') {
    throw new Error('Both text and pattern must be strings');
  }

  if (pattern.length === 0) return 0;
  if (pattern.length > text.length) return -1;

  // 构建部分匹配表
  const lps = new Array(pattern.length).fill(0);
  let len = 0;
  let i = 1;

  while (i < pattern.length) {
    if (pattern[i] === pattern[len]) {
      len++;
      lps[i] = len;
      i++;
    } else {
      if (len !== 0) {
        len = lps[len - 1];
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }

  // 执行搜索
  i = 0;
  let j = 0;

  while (i < text.length) {
    if (pattern[j] === text[i]) {
      i++;
      j++;
    }

    if (j === pattern.length) {
      return i - j;
    } else if (i < text.length && pattern[j] !== text[i]) {
      if (j !== 0) {
        j = lps[j - 1];
      } else {
        i++;
      }
    }
  }

  return -1;
};
